1. Field of the Invention
The present invention relates to an operation apparatus, a cache apparatus, and a control method thereof.
2. Description of the Related Art
There are many applications which request to determine whether or not each individual data included in a first data group matches at least some data in a second data group. Japanese Patent No. 3588487 proposes a counterflow pipeline technique so as to attain such determination. The counterflow pipeline technique will be described below with reference to FIG. 11. The counterflow pipeline technique uses first and second pipelines 1110 and 1120 as two pipelines. The first pipeline 1110 has a plurality of first nodes 1111, and these first nodes 1111 store data A[0] to A[3] of a first data group at a certain timing. The first pipeline 1110 shifts data in the right direction. As a result of the data shift, for example, the first node 1111 which stored data A[2] stores data A[3]. The second pipeline 1120 has a plurality of nodes 1121, and these second nodes 1121 store data B[0] to B[3] of a second data group at a certain timing. The second pipeline 1120 shifts data in the left direction. Determination units 1130 are connected to the first and second nodes 1111 and 1121, and determine whether or not data stored in these nodes match. With the counterflow pipeline technique, since data in the two pipelines are shifted in the opposing directions, data of the first and second groups are compared by a round-robin method.
In order to attain faster counterflow pipeline operations, the two pipelines are independently shifted. However, when the first and second pipelines 1110 and 1120 are shifted at the same time, some data may not be compared. For example, at a timing shown in FIG. 11, data A[2] and B[1] are compared. When the first and second pipelines are shifted at the same time, data A[2] is compared with data B[3] at the next timing. Therefore, data A[2] is never compared with data B[2]. In order to suppress such data comparison errors, in Japanese Patent No. 3588487, the statuses of nodes of the first and second pipelines 1110 and 1120 are monitored. In a status in which a data comparison error will occur, the two pipelines are stalled, and are allowed to shift data after completion of comparison. Furthermore, in the counterflow pipeline technique described in Japanese Patent No. 3588487, data undergo only one-to-one comparison processes, but one data cannot be simultaneously compared with a plurality of data or the number of data to be simultaneously compared with one data cannot be dynamically changed.